1. Field of the Invention
This invention relates to finite state machines and, more particularly, to a methodology and concomitant circuitry for coordinating the states of a finite state machine composed of two or more devices using a minimal number of interconnection wires among the devices.
2. Description of the Background
Flow control or event signaling in digital systems has traditionally been implemented using a master-slave arrangement. Conventionally, the master applies a voltage on one wire interconnecting the master and slave (the so-called "request" lead) to initiate flow control or event signaling, and the slave detects the applied voltage at its end of the wire. In turn, so as to inform the master that the slave has received the flow control or event signaling information, the slave applies a voltage on a second wire interconnecting the master and slave (the so-called "acknowledge" lead), and the master detects the applied voltage at its end of the second wire.
Typically, the request-acknowledge leads are used in conjunction with a data bus that also interconnects the master and slave in what is referred to in the art as the "two phase bundled data convention protocol". In this protocol, the master places data to be sent on a data bus and causes a request event by making a transition on the request lead. The slave takes the data from the data bus and signals the receipt of data as well as the ability to accept new data by making a transition on the acknowledge lead to thereby initiate an acknowledge event. There is a major difficulty with this protocol in that, while the control portion (i.e., the request-acknowledge communication) of the protocol is self-timed, the relationship between the control portion and the data bus is not delay insensitive. For instance, if the propagation delay of the data bus is substantially longer than the propagation delay of the request and acknowledge leads (e.g. due to path routing on a printed circuit board), the desired data may not be present on the data bus at the time the slave reads the bus.
Certain corrective arrangements or procedures have been implemented in an attempt to overcome the shortcomings of the foregoing protocol. The barrier to wide spread acceptance of these arrangements or procedures has been that they either doubled the number of wires, or relied upon multi-valued logic, or have not truly been delay insensitive.
In addition, the master-slave convention is asymmetric in that the master always transmits data and the slave always detects data--a symmetric system does not differentiate between the two devices terminating the ends of the interconnecting wires, and either device could initiate the transmission of information.